package main

import "fmt"

//#link: https://leetcode-cn.com/problems/minimum-number-of-days-to-make-m-bouquets/
func main() {
	bloomDay := []int{1, 10, 3, 10, 2}
	m := 3
	k := 1
	fmt.Println(minDays(bloomDay, m, k))
}

//采用二分法，若存在最小天数day，则[0，day)范围内全部为false,[day,max)全部为true
func minDays(bloomDay []int, m int, k int) int {
	flowers := len(bloomDay)
	//最少需要m*k多花
	if m*k > flowers {
		return -1
	}
	l, r := 1, 1
	for i := 0; i < flowers; i++ {
		r = max(r, bloomDay[i])
	}

	for l < r {
		days := (r-l)>>1 + l
		//可以开的话往中间段找
		if canComplete(bloomDay, m, k, days) {
			r = days
		} else {
			//不能满足的话说明天数太小了
			l = days + 1
		}
	}
	return l
}

func canComplete(bloomDay []int, m, k, days int) bool {
	flowerCount, bouquets := 0, 0
	for i := 0; i < len(bloomDay) && bouquets < m; i++ {
		//判断花是否开了
		if bloomDay[i] <= days {
			//开的花加1
			flowerCount++
			//当开的话与所需花束花的数量一致时，花束加一，开花的数量为0
			if flowerCount == k {
				bouquets++
				flowerCount = 0
			}
		} else {
			flowerCount = 0
		}
	}
	return bouquets >= m
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
